#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
  pub val: i32,
  pub next: Option<Box<ListNode>>
}

impl ListNode {
  #[inline]
  fn new(val: i32) -> Self {
    ListNode {
      next: None,
      val
    }
  }
}

// 2
#[test]
fn test_add_two_number() {
    let l1 = construct_list(vec![2, 3, 4, 5]);
    // print_list(&l1);
    let l2 = construct_list(vec![1, 9, 9, 8]);
    let ans = add_two_numbers(l1, l2);
    print_list(&ans);
    println!("{}", 5432 + 8991);
}

fn add_two_numbers(l1: Option<Box<ListNode>>, l2: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
    let mut result = None;
    let mut ptr = &mut result;
    let mut pattern = (l1, l2, 0, 0); // node1, node2, carry, sum
    loop {
        pattern = match pattern {
            (Some(node1), Some(node2), carry, _) => {
                let sum = carry + node1.val + node2.val;
                if sum >= 10 {
                    (node1.next, node2.next, 1, sum - 10)
                } else {
                    (node1.next, node2.next, 0, sum)
                }
            },
            (Some(node1), None, carry, _) => {
                let sum = carry + node1.val;
                if sum >= 10 {
                    (node1.next, None, 1, sum - 10)
                } else {
                    (node1.next, None, 0, sum)
                }
            },
            (None, Some(node2), carry, _) => {
                let sum = carry + node2.val;
                if sum >= 10 {
                    (None, node2.next, 1, sum - 10)
                } else {
                    (None, node2.next, 0, sum)
                }
            }
            (None, None, 0, _) => break,
            (None, None, carry, _) => (None, None, 0, carry),
        };
        *ptr = Some(Box::new(ListNode::new(pattern.3)));
        ptr = &mut ptr.as_mut().unwrap().next;
    }
    result
}

pub fn carried(l1:Option<Box<ListNode>>,l2: Option<Box<ListNode>>,mut carry: i32) -> Option<Box<ListNode>> {
    if l1.is_none() && l2.is_none() && carry == 0{
        None
    } else {
        Some(Box::new(ListNode {
            next: carried (
                l1.and_then(|x| {carry += x.val; x.next}),
                l2.and_then(|x| {carry += x.val; x.next}),
                carry / 10
            ),
            val: carry % 10
        }))
    }
}

fn construct_list(nums: Vec<i32>) -> Option<Box<ListNode>> {
    let mut head = None;
    let mut ptr = &mut head;
    for v in nums.iter() {
        let node = Box::new(ListNode::new(*v));
        *ptr = Some(node);
        ptr = &mut ptr.as_mut().unwrap().next;
    }
    return head;
}

fn print_list(list: &Option<Box<ListNode>>) {
    let mut ptr = list;
    loop {
        match ptr {
            Some(node) => {
                print!("{} ", node.val);
                ptr = &node.next;
            },
            None => break,
        }
    }
    println!("");
}

// 328
fn my_odd_even_list(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
    if head.is_none() {
        return None;
    }
    let mut odd = Some(Box::new(ListNode::new(0)));
    let mut even = Some(Box::new(ListNode::new(0)));
    let mut is_odd = true;

    let mut p1 = &mut odd; // 两个指针
    let mut p2 = &mut even;
    let mut cur = head;
    while let Some(mut node) = cur {
        cur = node.next.take();
        if is_odd {
            p1.as_mut().unwrap().next = Some(node);
            p1 = &mut p1.as_mut().unwrap().next;
        } else {
            p2.as_mut().unwrap().next = Some(node);
            p2 = &mut p2.as_mut().unwrap().next;
        }
        is_odd = !is_odd;
    }
    if let Some(node) = even.unwrap().next {
        p1.as_mut().unwrap().next = Some(node);
    }
    return odd.unwrap().next;
}
 
// 328
fn odd_even_list(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
    // redo in my way
    if head.is_none() {
        return None;
    }
    let mut head = head.unwrap();
    let mut p1: &mut ListNode = head.as_mut();
    let head2 = p1.next.take();
    if let Some(mut head2) = head2 {
        let mut p2 = head2.as_mut();
        while p2.next.is_some() {
            p1.next = p2.next.take();
            p1 = &mut **p1.next.as_mut().unwrap(); // 手动解引用
            p2.next = p1.next.take();
            if p2.next.is_some() {
                // let tmp = p2.next.as_mut().unwrap();
                // p2 = tmp;
                p2 = p2.next.as_mut().unwrap(); // 利用Box自动解引用
            }
        }
        p1.next = Some(head2);
    }
    return Some(head);
}

#[test]
fn test_odd_even_list() {
    let l = construct_list(vec![1, 2, 3, 4 ,5 , 6]);
    print_list(&l);
    print_list(&my_odd_even_list(l));
}